"""
给你一个字符串 s，找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

示例 2： 输入：s = "cbbd" 输出："bb"

提示： 1 <= s.length <= 1000 s 仅由数字和英文字母组成
"""

class Solution:
# 定义一个函数，参数为字符串s，返回值为最长回文串
    def longestPalindrome(self, s: str) -> str:
        # 获取字符串s的长度
        n = len(s)
        # 如果字符串长度小于2，则直接返回字符串
        if n < 2:
            return s
        # 初始化起始位置和最大回文串长度
        start, max_len = 0, 1
        # dp[i][j] 表示 s[i...j] 是否是回文串
        # 初始化一个二维数组dp，dp[i][j]表示s[i...j]是否是回文串
        dp = [[False] * n for _ in range(n)]
        # 遍历字符串s，从第二个字符开始
        for j in range(1, n):
            # 遍历每一个字符，从第一个字符开始
            for i in range(j):
                # 如果s[i]和s[j]相等，且s[i...j]的长度小于3或者dp[i+1][j-1]为True，则dp[i][j]为True
                if s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    # 如果dp[i][j]为True，且dp[i][j]的长度大于max_len，则更新max_len和start
                    if j - i + 1 > max_len:
                        start = i
                        max_len = j - i + 1
        # 返回最长回文串
        return s[start: start + max_len]


if __name__ == '__main__':
    s = "bababccdd"
    print(Solution().longestPalindrome(s))